home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 15983 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.2 KB
  1. Path: news.microsoft.com!news
  2. From: a-cnadc@microsoft.com (Dann Corbit)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Fastest Sorting Algorithm?
  5. Date: 4 Apr 1996 18:53:49 GMT
  6. Organization: Microsoft Corporation
  7. Message-ID: <4k15rt$nbb@news.microsoft.com>
  8. References: <Dou55w.7MB@novice.uwaterloo.ca> <DpAxtI.3w9@undergrad.math.uwaterloo.ca>
  9. NNTP-Posting-Host: 157.57.171.202
  10. Mime-Version: 1.0
  11. X-Newsreader: WinVN 0.93.14
  12.  
  13. In article <DpAxtI.3w9@undergrad.math.uwaterloo.ca>, sckettle@undergrad.math.uwaterloo.ca says...
  14. >
  15. >In article <Dou55w.7MB@novice.uwaterloo.ca>,
  16. >Gerald Wang  <GTWANG@HELIX.Watstar.UWaterloo.CA> wrote:
  17. >>A classmate was recently asked during a job interview what is the fastest 
  18. >>method to sort an array of numbers. He replied "Use a quicksort." They 
  19. >>asked "And how would you make it faster still?" He couldn't come up with 
  20. >>much...end of interview.
  21. >>
  22. >>I know it's a vague question... Any ideas on what they were asking? Or 
  23. >>what the right answer is?
  24. >>
  25. >>Gerald
  26. >>
  27. >>-------------------------------------------------------------------------
  28. >>Gerald Wang
  29. >>http://www.csclub.uwaterloo.ca/~gtwang
  30. >>
  31. >>
  32. >
  33. >Well you could use a type of bucket sorting algorithm which is faster than
  34. >quicksort when sorting integers.  How to make it faster I don't know - you
  35. >don't really make algortithms faster you make code implementations of
  36. >algorithms faster. Mybe they meant tweaking stratigies for quicksort like how
  37. >to choose a pivot element.  Who knows. 
  38. Bucket sort, counting sort and radix sort are all faster if there are a 
  39. large number of elements.
  40.  
  41. Their question about how to make it faster still was probably to see how
  42. he tackles problems.  They may have wanted something like:
  43. 1.  Research avalable sorting algorithms
  44. 2.  Select best algorithm for problem space
  45. 3.  Profile the chosen implementation to find bottlenecks
  46. 4.  Optimize the small fraction of code that is the greatest bottleneck.
  47.  
  48. Alternatives:
  49. 1.  Buy a sorting package
  50. 2.  Use a database to do the sorting
  51.  
  52. -- 
  53. The opinions expressed in this message are my own personal views
  54. and do not reflect the official views of Microsoft Corporation.
  55. In fact, I'm just a subcontractor, not an employee, so pull in your claws.
  56.  
  57.